package top.jolyoulu.力扣._1017_负二进制转换;

import top.jolyoulu.utils.TimerUtils;

//给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。
//
// 注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。
//
//
//
// 示例 1：
//
//
//输入：n = 2
//输出："110"
//解释：(-2)² + (-2)¹ = 2
//
//
// 示例 2：
//
//
//输入：n = 3
//输出："111"
//解释：(-2)² + (-2)¹ + (-2)⁰ = 3
//
//
// 示例 3：
//
//
//输入：n = 4
//输出："100"
//解释：(-2)² = 4
//
//
//
//
// 提示：
//
//
// 0 <= n <= 10⁹
//
//
// Related Topics 数学 👍 79 👎 0
public class Answer1 {

    /*
        思路：与10进制换2进制思路一样，将n一直除-2取余数拼接
        注意：与换二进制不同之处，当余数0时不处理，当余数非0时需要将n的末尾减去1再除2
    */
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            sb.insert(0, Math.abs(n % -2));
            n = n % -2 == 0 ? n / -2 : (n - 1) / -2;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Answer1 answer1 = new Answer1();
        System.out.println("用例1=======================================");
        System.out.println("n = 2");
        TimerUtils.timer(() -> {
            System.out.println(answer1.baseNeg2(2));
        });
        System.out.println("用例2=======================================");
        System.out.println("n = 3");
        TimerUtils.timer(() -> {
            System.out.println(answer1.baseNeg2(3));
        });
        System.out.println("用例3=======================================");
        System.out.println("n = 4");
        TimerUtils.timer(() -> {
            System.out.println(answer1.baseNeg2(4));
        });
        System.out.println("用例4=======================================");
        System.out.println("n = 6");
        TimerUtils.timer(() -> {
            System.out.println(answer1.baseNeg2(6));
        });
    }
}
